SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Kleene's algorithm</title>

</head>

Kleene's algorithm

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, in particular in <a href="Formal_language_theory" class="mw-redirect" title="Formal language theory">formal language theory</a>, Kleene's algorithm transforms a given <a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">nondeterministic finite automaton</a> (NFA) into a <a href="Regular_expression" title="Regular expression">regular expression</a>.

Together with other conversion algorithms, it establishes the equivalence of several description formats for <a href="Regular_language" title="Regular language">regular languages</a>. Alternative presentations of the same method include the "elimination method" attributed to <a href="Janusz_Brzozowski_(computer_scientist)" title="Janusz Brzozowski (computer scientist)">Brzozowski</a> and <a href="Edward_J._McCluskey" title="Edward J. McCluskey">McCluskey</a>, the algorithm of <a href="Robert_McNaughton" title="Robert McNaughton">McNaughton</a> and <a href="Hisao_Yamada" title="Hisao Yamada">Yamada</a>,<a href="#cite_note-1">[1]</a> and the use of <a href="Arden's_lemma" class="mw-redirect" title="Arden's lemma">Arden's lemma</a>.

<div class="mw-heading mw-heading2"><h2 id="Algorithm_description">Algorithm description</h2></div>

According to Gross and Yellen (2004),<a href="#cite_note-gross2004handbook-2">[2]</a> the algorithm can be traced back to <a href="Kleene" class="mw-redirect" title="Kleene">Kleene</a> (1956).<a href="#cite_note-3">[3]</a> A presentation of the algorithm in the case of <a href="Deterministic_finite_automata" class="mw-redirect" title="Deterministic finite automata">deterministic finite automata</a> (DFAs) is given in Hopcroft and Ullman (1979).<a href="#cite_note-4">[4]</a> The presentation of the algorithm for NFAs below follows Gross and Yellen (2004).<a href="#cite_note-gross2004handbook-2">[2]</a>

Given a <a href="Nondeterministic_finite_automaton#Formal_definition" title="Nondeterministic finite automaton">nondeterministic finite automaton</a> M = (Q, Σ, δ, q0, F), with Q = { q0,...,qn } its set of <a href="Nondeterministic_finite_automaton#Formal_definition" title="Nondeterministic finite automaton">states</a>, the algorithm computes

<dl><dd>the sets Rk ij of all strings that take M from state qi to qj without going through any state numbered higher than k.</dd></dl>

Here, "going through a state" means entering and leaving it, so both i and j may be higher than k, but no intermediate state may.

Each set Rk ij is represented by a regular expression; the algorithm computes them step by step for k = -1, 0, ..., n. Since there is no state numbered higher than n, the regular expression Rn 0j represents the set of all strings that take M from its <a href="Nondeterministic_finite_automaton#Formal_definition" title="Nondeterministic finite automaton">start state</a> q0 to qj. If F = { q1,...,qf } is the set of <a href="Nondeterministic_finite_automaton#Formal_definition" title="Nondeterministic finite automaton">accept states</a>, the <a href="Regular_expression#Formal_definition" title="Regular expression">regular expression</a> Rn 01 | ... | Rn 0f represents the language <a href="Nondeterministic_finite_automaton#Formal_definition" title="Nondeterministic finite automaton">accepted</a> by M.

The initial regular expressions, for k = -1, are computed as follows for i≠j:

and as follows for i=j:

In other words, R−1 ij mentions all letters that label a transition from i to j, and we also include ε in the case where i=j.

After that, in each step the expressions Rk ij are computed from the previous ones by

Another way to understand the operation of the algorithm is as an "elimination method", where the states from 0 to n are successively removed: when state k is removed, the regular expression Rk-1 ij, which describes the words that label a path from state i>k to state j>k, is rewritten into Rk ij so as to take into account the possibility of going via the "eliminated" state k.

By induction on k, it can be shown that the length<a href="#cite_note-5">[5]</a> of each expression Rk ij is at most <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠1/3⁠(4k+1(6s+7) - 4) symbols, where s denotes the number of characters in Σ.

Therefore, the length of the regular expression representing the language accepted by M is at most ⁠1/3⁠(4n+1(6s+7)f - f - 3) symbols, where f denotes the number of final states.

This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size.<a href="#cite_note-6">[6]</a>

In practice, the size of the regular expression obtained by running the algorithm can be very different depending on the order in which the states are considered by the procedure, i.e., the order in which they are numbered from 0 to n.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

The automaton shown in the picture can be described as M = (Q, Σ, δ, q0, F) with

<ul><li>the set of states Q = { q0, q1, q2 },</li>

<li>the input alphabet Σ = { a, b },</li>

<li>the transition function δ with δ(q0,a)=q0,   δ(q0,b)=q1,   δ(q1,a)=q2,   δ(q1,b)=q1,   δ(q2,a)=q1, and δ(q2,b)=q1,</li>

<li>the start state q0, and</li>

<li>set of accept states F = { q1 }.</li></ul>

Kleene's algorithm computes the initial regular expressions as

<td>R−1 00

</td>

<td>= a | ε

</td></tr>

<tr>

</td>

<td>= b

</td></tr>

<tr>

</td>

<td>= ∅

</td></tr>

<tr>

</td>

<td>= ∅

</td></tr>

<tr>

</td>

<td>= b | ε

</td></tr>

<tr>

</td>

<td>= a

</td></tr>

<tr>

</td>

<td>= ∅

</td></tr>

<tr>

</td>

<td>= a | b

</td></tr>

<tr>

</td>

<td>= ε

</td></tr></tbody></table></dd></dl>

After that, the Rk ij are computed from the Rk-1 ij step by step for k = 0, 1, 2.

<a href="Kleene_algebra" title="Kleene algebra">Kleene algebra</a> equalities are used to simplify the regular expressions as much as possible.

<td>R0 00

</td>

<td>= R−1 00 (R−1 00)* R−1 00 | R−1 00

</td>

<td>= (a | ε)

</td>

<td>(a | ε)*

</td>

<td>(a | ε)

</td>

<td>| a | ε

</td>

<td>= a*

</td></tr>

<tr>

<td>R0 01

</td>

<td>= R−1 00 (R−1 00)* R−1 01 | R−1 01

</td>

<td>= (a | ε)

</td>

<td>(a | ε)*

</td>

<td>b

</td>

<td>| b

</td>

<td>= a* b

</td></tr>

<tr>

<td>R0 02

</td>

<td>= R−1 00 (R−1 00)* R−1 02 | R−1 02

</td>

<td>= (a | ε)

</td>

<td>(a | ε)*

</td>

<td>∅

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R0 10

</td>

<td>= R−1 10 (R−1 00)* R−1 00 | R−1 10

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>(a | ε)

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R0 11

</td>

<td>= R−1 10 (R−1 00)* R−1 01 | R−1 11

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>b

</td>

<td>| b | ε

</td>

<td>= b | ε

</td></tr>

<tr>

<td>R0 12

</td>

<td>= R−1 10 (R−1 00)* R−1 02 | R−1 12

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>∅

</td>

<td>| a

</td>

<td>= a

</td></tr>

<tr>

<td>R0 20

</td>

<td>= R−1 20 (R−1 00)* R−1 00 | R−1 20

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>(a | ε)

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R0 21

</td>

<td>= R−1 20 (R−1 00)* R−1 01 | R−1 21

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>b

</td>

<td>| a | b

</td>

<td>= a | b

</td></tr>

<tr>

<td>R0 22

</td>

<td>= R−1 20 (R−1 00)* R−1 02 | R−1 22

</td>

<td>= ∅

</td>

<td>(a | ε)*

</td>

<td>∅

</td>

<td>| ε

</td>

<td>= ε

</td></tr></tbody></table></dd></dl>

<td>R1 00

</td>

<td>= R0 01 (R0 11)* R0 10 | R0 00

</td>

<td>= a*b

</td>

<td>(b | ε)*

</td>

<td>∅

</td>

<td>| a*

</td>

<td>= a*

</td></tr>

<tr>

<td>R1 01

</td>

<td>= R0 01 (R0 11)* R0 11 | R0 01

</td>

<td>= a*b

</td>

<td>(b | ε)*

</td>

<td>(b | ε)

</td>

<td>| a* b

</td>

<td>= a* b* b

</td></tr>

<tr>

<td>R1 02

</td>

<td>= R0 01 (R0 11)* R0 12 | R0 02

</td>

<td>= a*b

</td>

<td>(b | ε)*

</td>

<td>a

</td>

<td>| ∅

</td>

<td>= a* b* ba

</td></tr>

<tr>

<td>R1 10

</td>

<td>= R0 11 (R0 11)* R0 10 | R0 10

</td>

<td>= (b | ε)

</td>

<td>(b | ε)*

</td>

<td>∅

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R1 11

</td>

<td>= R0 11 (R0 11)* R0 11 | R0 11

</td>

<td>= (b | ε)

</td>

<td>(b | ε)*

</td>

<td>(b | ε)

</td>

<td>| b | ε

</td>

<td>= b*

</td></tr>

<tr>

<td>R1 12

</td>

<td>= R0 11 (R0 11)* R0 12 | R0 12

</td>

<td>= (b | ε)

</td>

<td>(b | ε)*

</td>

<td>a

</td>

<td>| a

</td>

<td>= b* a

</td></tr>

<tr>

<td>R1 20

</td>

<td>= R0 21 (R0 11)* R0 10 | R0 20

</td>

<td>= (a | b)

</td>

<td>(b | ε)*

</td>

<td>∅

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R1 21

</td>

<td>= R0 21 (R0 11)* R0 11 | R0 21

</td>

<td>= (a | b)

</td>

<td>(b | ε)*

</td>

<td>(b | ε)

</td>

<td>| a | b

</td>

<td>= (a | b) b*

</td></tr>

<tr>

<td>R1 22

</td>

<td>= R0 21 (R0 11)* R0 12 | R0 22

</td>

<td>= (a | b)

</td>

<td>(b | ε)*

</td>

<td>a

</td>

<td>| ε

</td>

<td>= (a | b) b* a | ε

</td></tr></tbody></table></dd></dl>

<td>R2 00

</td>

<td>= R1 02 (R1 22)* R1 20 | R1 00

</td>

<td>= a*b*ba

</td>

<td>((a|b)b*a | ε)*

</td>

<td>∅

</td>

<td>| a*

</td>

<td>= a*

</td></tr>

<tr>

<td>R2 01

</td>

<td>= R1 02 (R1 22)* R1 21 | R1 01

</td>

<td>= a*b*ba

</td>

<td>((a|b)b*a | ε)*

</td>

<td>(a|b)b*

</td>

<td>| a* b* b

</td>

<td>= a* b (a (a | b) | b)*

</td></tr>

<tr>

<td>R2 02

</td>

<td>= R1 02 (R1 22)* R1 22 | R1 02

</td>

<td>= a*b*ba

</td>

<td>((a|b)b*a | ε)*

</td>

<td>((a|b)b*a | ε)

</td>

<td>| a* b* ba

</td>

<td>= a* b* b (a (a | b) b*)* a

</td></tr>

<tr>

<td>R2 10

</td>

<td>= R1 12 (R1 22)* R1 20 | R1 10

</td>

<td>= b* a

</td>

<td>((a|b)b*a | ε)*

</td>

<td>∅

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R2 11

</td>

<td>= R1 12 (R1 22)* R1 21 | R1 11

</td>

<td>= b* a

</td>

<td>((a|b)b*a | ε)*

</td>

<td>(a|b)b*

</td>

<td>| b*

</td>

<td>= (a (a | b) | b)*

</td></tr>

<tr>

<td>R2 12

</td>

<td>= R1 12 (R1 22)* R1 22 | R1 12

</td>

<td>= b* a

</td>

<td>((a|b)b*a | ε)*

</td>

<td>((a|b)b*a | ε)

</td>

<td>| b* a

</td>

<td>= (a (a | b) | b)* a

</td></tr>

<tr>

<td>R2 20

</td>

<td>= R1 22 (R1 22)* R1 20 | R1 20

</td>

<td>= ((a|b)b*a | ε)

</td>

<td>((a|b)b*a | ε)*

</td>

<td>∅

</td>

<td>| ∅

</td>

<td>= ∅

</td></tr>

<tr>

<td>R2 21

</td>

<td>= R1 22 (R1 22)* R1 21 | R1 21

</td>

<td>= ((a|b)b*a | ε)

</td>

<td>((a|b)b*a | ε)*

</td>

<td>(a|b)b*

</td>

<td>| (a | b) b*

</td>

<td>= (a | b) (a (a | b) | b)*

</td></tr>

<tr>

<td>R2 22

</td>

<td>= R1 22 (R1 22)* R1 22 | R1 22

</td>

<td>= ((a|b)b*a | ε)

</td>

<td>((a|b)b*a | ε)*

</td>

<td>((a|b)b*a | ε)

</td>

<td>| (a | b) b* a | ε

</td>

<td>= ((a | b) b* a)*

</td></tr></tbody></table></dd></dl>

Since q0 is the start state and q1 is the only accept state, the regular expression R2 01 denotes the set of all strings accepted by the automaton.

<ul><li><a href="Floyd%E2%80%93Warshall_algorithm#Applications_and_generalizations" title="Floyd–Warshall algorithm">Floyd–Warshall algorithm</a> — an algorithm on weighted graphs that can be implemented by Kleene's algorithm using a particular <a href="Kleene_algebra#Examples" title="Kleene algebra">Kleene algebra</a></li>

<li><a href="Star_height_problem" title="Star height problem">Star height problem</a> — what is the minimum stars' nesting depth of all regular expressions corresponding to a given DFA?</li>

<li><a href="Generalized_star_height_problem" class="mw-redirect" title="Generalized star height problem">Generalized star height problem</a> — if a complement operator is allowed additionally in regular expressions, can the <a href="Star_height#Generalized_star_height" title="Star height">stars' nesting depth</a> of Kleene's algorithm's output be limited to a fixed bound?</li>

<li><a href="Thompson's_construction_algorithm" class="mw-redirect" title="Thompson's construction algorithm">Thompson's construction algorithm</a> — transforms a regular expression to a finite automaton</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMcNaughtonYamada1960" class="citation journal cs1">McNaughton, R.; Yamada, H. (March 1960). "Regular Expressions and State Graphs for Automata". IRE Transactions on Electronic Computers. EC-9 (1): 39–47. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTEC.1960.5221603">10.1109/TEC.1960.5221603</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0367-9950">0367-9950</a>.</cite>

</li>

<li id="cite_note-gross2004handbook-2">^ <a href="#cite_ref-gross2004handbook_2-0">a</a> <a href="#cite_ref-gross2004handbook_2-1">b</a> <cite id="CITEREFJonathan_L._Gross_and_Jay_Yellen2004" class="citation book cs1">Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58488-090-2</bdi>.</cite> Here: sect.2.1, remark R13 on p.65

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFKleene,_Stephen_C.1956" class="citation journal cs1">Kleene, Stephen C. (1956). <a rel="nofollow" class="external text" href="http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf">"Representation of Events in Nerve Nets and Finite Automata"</a> (PDF). Automata Studies, Annals of Math. Studies. 34. Princeton Univ. Press.</cite> Here: sect.9, p.37-40

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFJohn_E._Hopcroft,_Jeffrey_D._Ullman1979" class="citation book cs1">John E. Hopcroft, Jeffrey D. Ullman (1979). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoau00hopc">Introduction to Automata Theory, Languages, and Computation</a>. Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-02988-X</bdi>.</cite> Here: Section 3.2.1 pages 91-96

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> More precisely, the number of regular-expression symbols, "ai", "ε", "|", "*", "·"; not counting parentheses.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFGruberHolzer2008" class="citation book cs1">Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 5126. Springer Berlin Heidelberg. pp. 39–50. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-70583-3_4">10.1007/978-3-540-70583-3_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540705833</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10975422">10975422</a>.</cite>. Theorem 16.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-14" href="https://en.wikipedia.org/wiki/?title=Kleene's_algorithm&oldid=1285525439">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>